import jdk.internal.org.objectweb.asm.tree.InnerClassNode;
import sun.reflect.generics.tree.Tree;

import javax.print.DocFlavor;
import java.util.*;
import java.util.concurrent.ThreadPoolExecutor;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
    }
}


class Solution {
    boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode tmp=queue.poll();
                if(tmp!=null){
                    queue.offer(tmp.left);
                    queue.offer(tmp.right);
                }else{
                    break;
                }
            }
            while(!queue.isEmpty()){
                if(queue.poll()!=null){
                    return false;
                }
            }
        }
        return true;
    }







    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        if(root!=null){
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> ret=new ArrayList<>();
                while(size!=0){
                    TreeNode tmp=queue.poll();
                    ret.add(tmp.val);
                    if(tmp.left!=null){
                        queue.offer(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.offer(tmp.right);
                    }
                    size--;
                }
                list.add(ret);
            }
        }
        return list;
    }






    void leve(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode tmp=queue.poll();
                System.out.print(tmp.val);
                if(tmp.left!=null){
                    queue.offer(tmp.left);
                }
                if(tmp.right!=null){
                    queue.offer(tmp.right);
                }
            }
        }
    }





    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode lestTree=mirrorTree(root.left);
        TreeNode rightTree=mirrorTree(root.right);
        root.left=rightTree;
        root.right=lestTree;
        return root;
    }




    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();
        if(root!=null){
            stack.push(root);
            while(!stack.empty()){
                TreeNode tmp=stack.pop();
                list.add(tmp.val);
                if(tmp.right!=null){
                    stack.push(tmp.right);
                }
                if(tmp.left!=null){
                    stack.push(tmp.left);
                }
            }
        }
        return list;
    }


    public List<Integer> inorderTraversal(TreeNode head){
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(head!=null){
            while(!stack.empty()||head!=null){
                if(head!=null){
                    stack.push(head);
                    head=head.left;
                }else{
                    head=stack.pop();
                    list.add(head.val);
                    head=head.right;
                }
            }
        }
        return list;
    }
    public List<Integer> postorderTraversal(TreeNode head){
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> s1=new Stack<>();
        Stack<TreeNode> s2=new Stack<>();
        if(head!=null){
            s1.push(head);
            while(!s1.empty()){
                head=s1.pop();
                s2.push(head);
                if(head.left!=null){
                    s1.push(head.left);
                }
                if(head.right!=null){
                    s1.push(head.right);
                }
            }
            while(!s2.empty()){
                list.add(s2.pop().val);
            }
        }
        return list;
    }





    public TreeNode roots;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode curTree=new TreeNode(-1);
        roots=curTree;
        inorder(root);
        return curTree.right;
    }
    public void inorder(TreeNode node){
        if(node==null){
            return;
        }
        inorder(node.left);
        roots.right=node;
        node.left=null;
        roots=node;
        inorder(node.right);
    }




    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null){
            return root2;
        }
        if(root2==null){
            return root1;
        }
        TreeNode root= new TreeNode(root1.val+root2.val);
        root.left=mergeTrees(root1.left,root2.left);
        root.right=mergeTrees(root1.right,root2.right);
        return root;
    }
}
class Node{

    public int val;
    public Node left;
    public Node right;

    public Node(){}

    public Node(int val) {
        this.val = val;
    }

    //前序遍历

    public void preOrderTraversal(Node root){
        if(root==null){
            return ;
        }
        System.out.print(root.val);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
    //中序遍历

    public void inOrderTraversal(Node root){
        if(root==null){
            return ;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val);
        inOrderTraversal(root.right);
    }
    //后续遍历

    public void postOrderTraversal(Node root){
        if(root==null){
            return ;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val);
    }
    // 遍历思路-求结点个数
    static int size = 0;
    void getSize1(Node root){
        if(root==null){
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);

    }

    // 子问题思路-求结点个数
    int getSize2(Node root){
        if(root==null){
            return 0;
        }
        return getSize2(root.left)+getSize2(root.right)+1;
    }

    // 遍历思路-求叶子结点个数
    static int leafSize = 0;
    void getLeafSize1(Node root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    // 子问题思路-求叶子结点个数
    int getLeafSize2(Node root){
        if(root==null){
            return 0;
        }
        if(root.right==null&&root.left==null){
            return 1;
        }
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }


    // 子问题思路-求第 k 层结点个数
    int getKLevelSize(Node root,int k){
        if(k==1){
            return 1;
        }
        return getKLevelSize(root.left,k-1)+ getKLevelSize(root.right,k-1);
    }

    // 获取二叉树的高度
    int getHeight(Node root){
        if(root==null){
            return 0;
        }
        int l=getHeight(root.left);
        int r=getHeight(root.right);
        return Math.max(l,r)+1;
    }

}
public class MyTree {

}
